package com.leetcode.dynamic_programming;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/8/13 22:25
 */
public class SuperEggDrop_887 {

    public int superEggDrop(int K, int N) {
        final int[][] dp = new int[K + 1][N + 1];
        // i - 还剩多少个鸡蛋; j - 楼层号
        int m = 1;
        for (; dp[K][m] < N; m++)
            for (int k = 1; k <= K; k++)
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        return m;
    }

    static class Solution {
        public int superEggDrop(int K, int N) {
            int[][] memo = new int[K + 1][N + 1];
            for (int i = 1; i <= K; i++) {
                Arrays.fill(memo[i], -1);
            }
            return dp(K, N, memo);
        }

        private int dp(int K, int N, int[][] memo) {
            if (K == 1) return N;
            if (N == 0) return 0;
            if (memo[K][N] != -1)
                return memo[K][N];

            int res = Integer.MAX_VALUE;
            // 穷举所有情况
            for (int i = 1; i <= N; i++) {
                // 两种状态
                // 要求最坏情况，所以求较大值
                int temp = Math.max(
                        // 鸡蛋打碎，那么一定是在当前楼层往下
                        dp(K - 1, i - 1, memo),
                        // 鸡蛋没碎，那么一定是在当前楼层往上
                        dp(K, N - i, memo))
                        // 在第i楼扔了一次
                        + 1;
                // 求所有尝试中的最小值
                res = Math.min(temp, res);
            }
            memo[K][N] = res;
            return res;
        }

    }

}
